      1  import java.util.HashMap;

      2  import java.util.Map;

      3  import java.util.PriorityQueue;

      4

      5  /**

      6     A tree for decoding Huffman codes.

      7  */

      8  public class HuffmanTree

      9  {

     10     private Node root;

     11

     12     /**

     13        Constructs a Huffman tree from given character frequencies.

     14        @param frequencies a map whose keys are the characters to be encoded

     15        and whose values are the frequencies of the characters

     16     */

     17     public HuffmanTree(Map<Character, Integer> frequencies)

     18     {

     19        PriorityQueue<Node> nodes = new PriorityQueue<Node>();

     20        for (char ch : frequencies.keySet())

     21        {

     22           Node newNode = new Node();

     23           newNode.character = ch;

     24           newNode.frequency = frequencies.get(ch);

     25           nodes.add(newNode);

     26        }

     27

     28        while (nodes.size() > 1)

     29        {

     30           Node smallest = nodes.remove();

     31           Node nextSmallest = nodes.remove();

     32           Node newNode = new Node();

     33           newNode.frequency = smallest.frequency + nextSmallest.frequency;

     34           newNode.left = smallest;

     35           newNode.right = nextSmallest;

     36           nodes.add(newNode);

     37        }

     38

     39        root = nodes.remove();

     40     }

     41

     42     /**

     43        Decodes an encoded string.

     44        @param input a string made up of 0 and 1

     45     */

     46     public String decode(String input)

     47     {

     48        String result = "";

     49        Node n = root;

     50        for (int i = 0; i < input.length(); i++)

     51        {

     52           char ch = input.charAt(i);

     53           if (ch == '0')

     54           {

     55              n = n.left;

     56           }

     57           else

     58           {

     59              n = n.right;

     60           }

     61           if (n.left == null) // n is a leaf

     62           {

     63              result = result + n.character;

     64              n = root;

     65           }

     66        }

     67        return result;

     68     }

     69

     70     public Map<Character, String> getEncodingMap()

     71     {

     72        Map<Character, String> map = new HashMap<Character, String>();

     73        if (root != null) { root.fillEncodingMap(map, ""); }

     74        return map;

     75     }

     76

     77     class Node implements Comparable<Node>

     78     {

     79        public char character;

     80        public int frequency;

     81        public Node left;

     82        public Node right;

     83

     84        public int compareTo(Node other) { return frequency - other.frequency; }

     85

     86        public void fillEncodingMap(Map<Character, String> map, String prefix)

     87        {

     88           if (left == null) // it's a leaf

     89           {

     90              map.put(character, prefix);

     91           }

     92           else

     93           {

     94              left.fillEncodingMap(map, prefix + "0");

     95              right.fillEncodingMap(map, prefix + "1");

     96           }

     97        }

     98     }

     99  }

    100